﻿/*
 *	Filename: wuyaowei_first_node.c
 *	 Version: 0.1.0
 *   Description: 输出环的第一个节点
 *
 *        Author: wuyaowei
 *          Date: 2020-06-20
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
  char data;
  struct Node * next;
}Node;

/*
 *  创建节点
 */
Node * createNode(int val) {
  Node *node = (Node *)malloc(sizeof(Node));
  node->data = val;
  node->next = NULL;
  return node;
}

Node *head = NULL;

/*
 * 使用快慢指针：
 * 1、链表起始位置到环节点位置为a
 * 2、相遇时慢指针走的步数为a+b1(b1为环节首节点到慢指针当前位置的距离)；
 * 3、快指针走的步数为a+b1+b2+b1(b2为慢指针当前位置到环首节点的距离);
 * 4、快指针走的步数是慢指针两倍，因此 2*(a + b) = a + b1 + b2 + b1; ==> (a = b2) 
 * 5、因此当快慢指针相遇时，慢指针继续向前走，同时指针从链表头向前走，两个指针相遇时就是环的节点位置；
 * 
 */
Node* firstNodeInLoop(Node *head) {
  Node *fast = head;
  Node *slow = head;
  if (NULL == head || NULL == head->next) {
    return NULL;
  }

  while(NULL != fast && NULL != fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if(slow == fast) {
      break;
    }
  }
  
  Node *p = head; 
  while(NULL != p) {
    if(p == slow) {
      break;
    }
    slow = slow->next;
    p = p->next;
  }

  return p;
  
}
  
void main() {
  int L = 0, N = 0;
  printf("输入链表长度：\n");
  scanf("%d", &L);
  printf("输入环的首节点坐标(0代表没有环)：\n");
  scanf("%d", &N);
  //初始化单链表
  Node *T = NULL, *p = NULL;
  if (N == 0) {
    for (int i = 0; i < L; i++) {
      Node *t1 = createNode(i+1);
      if (i == 0) {
        head = t1;
        p = t1;
        continue;
      }
      p->next = t1;
      p = t1;
    }
  } else {
    for (int i = 0; i < L; i++) {
      Node *t1 = createNode(i+1);
      if (i == (N-1)) {
        T = t1;
      }
      if ((i == 0)) {
        head = t1;
        p = t1;
        continue;
      }
      p->next = t1;
      p = t1;
    }
    p->next = T;
  }

  Node *first = firstNodeInLoop(head);
  printf("进入环的第一个节点为：%d \n", first->data); 

}
